#ifndef __GRAPH_H__
#define __GRAPH_H__

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define VERY_BIG 65535

//类型声明
#define MAXN 1024  //图中最大的顶点个数
typedef char VType;//顶点的元素类型
typedef int AdjType;//边的元素类型

typedef struct graph
{
    //一个一维数组存储图G的顶点集合V
    VType V[MAXN];
    //一个二维数组存储图G的关系集合
    AdjType A[MAXN][MAXN];
    //顶点数量
    int vexnum;
    //变得条数
    int arcnum;
}Graph;//图的类型


//函数声明

/*
createGraph:根据用户输入的顶点和关系建立一个图(邻接矩阵)
            顶点和关系通过键盘输入
返回值:
    返回建立好的图的地址
*/
Graph *createGraph();

/*
chIndex:返回指定元素ch在数组中第一次出现的下标,如果数组中不存在ch则返回-1
@ch:你要查找下标的字符
@str:数组的首地址
@num:数组中的元素个数
返回值:
    指定元素ch在数组中第一次出现的下标,如果数组中不存在ch则返回-1
*/
int chIndex(VType ch,VType *str,int num);


/*
printGraph:打印一个指定的图(顶点数组,邻接矩阵)
        验证图是否保存成功
@g:指针,指向你要打印的图
返回值:无
*/
void printGraph(Graph *g);

/*
DFS:从图g中下标为v的顶点开始,以深度优先搜索算法遍历图g的顶点
    图g中可能某些顶点不能从v到达
@g:指针,指向你要遍历的图的地址
@v:下标,表示你要从哪一个顶点开始遍历(顶点数组的下标)
返回值:无
*/
void DFS(Graph *g,int v);

/*
getFirstAdj:获取图g中顶点v的第一个邻接点的下标
@g:指针,指向你要操作的图的地址
@v:下标,表示你要获取哪一个顶点的第一个邻接点
返回值:
    如果有邻接点,返回v的第一个邻接点的下标
    如果没有就返回-1
*/
int getFirstAdj(Graph *g,int v);


/*
getNextAdj:获取图g中顶点v基于vi的下一个邻接点的下标
@g:指针,指向你要操作的图的地址
@v:下标,表示你要获取哪一个顶点的下一个邻接点
@vi:下标,表示你要获取v的vi邻接点的下一个邻接点
返回值:
    如果有邻接点,返回v的第一个邻接点的下标
    如果没有就返回-1
*/
int getNextAdj(Graph *g,int v,int vi);

/*
DFStravel:以深度优先搜索的思想遍历图g,保证每一个节点都可以遍历到
@g:指针,指向你要操作的图的地址
返回值:无
*/
void DFStravel(Graph *g);



#endif